7482. Торговля
Вдоль трассы Алматы-Тараз есть n населенных пунктов, пронумерованных числами от 1 до n. В начале зимы m неизвестных торговцев привезли из неизвестного аула вязаные шапки
и начали ими торговать в этих населенных пунктах. У этих торговцев есть два
принципа: не торговать в одном месте более одного раза (один день) и с каждым
днем увеличивать цену на шапку.
Более формально каждый i-ый
торговец:
·
Начинает торговать в населенном пункте li со стартовой ценой на одну
шапку xi;
·
Каждый день переходит в соседний населенный пункт, то
есть, если вчера он торговал в населенном пункте j, то сегодня торгует в населенном пункте j + 1;
·
Каждый день увеличивает цену на 1, то есть, если вчера
цена на его шапки была x, то сегодня
цена x + 1;
·
Завершает торговать в населенном пункте ri (при этом в пункте ri торговля происходит).
Наша задача для каждого населенного пункта определить
максимальную цену на одну шапку за всю историю.
Вход. В первой строке находятся два целых числа n (1 ≤ n ≤ 300000) и m (1
≤ m ≤ 300000) –
количество населенных пунктов и количество торговцев соответственно.
В каждой из следующих m
строк находятся по три целых числа li,
ri (1 ≤ li ≤ ri ≤ n) и xi
(1 ≤ xi ≤ 109)
– номера начального и конечного населенных пунктов и начальная цена на шапку
для i-го торговца соответственно.
Выход. Выведите n целых чисел, разделенных пробелом, где
i-ое число равно максимальной цене на
одну шапку за всю историю продаж i-ого
населенного пункта. Если в каком-то населенном пункте никто не торговал
шапками, то для этого населенного пункта выведите 0.
|
Пример
входа |
Пример
выхода |
|
5 2 1 3 2 2 4 6 |
2 6 7 8 0 |
РЕШЕНИЕ
структуры данных – дерево отрезков
Анализ алгоритма
Заведем дерево
отрезков [1; n], изначально обнулим
его. Пусть торговец продавал шапки в населенных пунктах [li; ri],
начиная с цены pi. Разобьем
[li; ri] на фундаментальные отрезки [lx1; ry1],
[lx2; ry2], …, [lxk;
ryk]. Тогда в вершину,
которой соответствует интервал [lxq;
ryq] (1 ≤ q ≤ k), занесем число pi
+ сумма длин интервалов [lxt;
ryt], для всех t < q.
Например, пусть n = 5 и первая торговля состоится в
городах с номерами от 2 до 5, начиная с цены 4. Отрезок [2; 5] распадется на
фундаментальные [2; 2] + [3; 3] + [4; 5] и дерево отрезков после обработки
первой операции будет выглядеть следующим образом:
Если
фундаментальный отрезок [a; b] содержит значение p, то это означает что:
·
торговец продавал шапки во всех городах от a до b.
·
торговец в городе a
продал шапку по цене p, в городе a + 1 продал шапку по цене p + 1, и так далее, и наконец в городе b продал шапку по цене p + b
– a.
Рассмотрим
процедуру выполнения запроса [Left; Right] (отрезок, на котором торговец
продает шапки) на отрезке [LeftPos; RightPos], если цена шапки начинается с x.
В левом сыне
торговец будет продавать шапки в len
= min(Middle, Right) – Left + 1
городах, начиная с цены x. В правом
сыне в первом городе, куда придет торговец, цена шапки составит x + len.
То есть в городах с номерами [max(Left,
Middle + 1), Right] торговец будет продавать шапки, начиная с цены x + len.
Однако если len < 0 (это возможно
если отрезок запроса целиком лежит в правом сыне), то следует положить len = 0.
Пусть отрезок [a; b]
имеет двух сыновей [a; m] и [m + 1; b]. Если торговец
в городе a продал шапку по цене p, то в городе m + 1 он продал шапку по цене p
+ m + 1 – a.
В процессе
выполнения запросов реализуем проталкивание, поддерживающее максимум:
Для вывода
ответа следует пройти по дереву, протолкнуть все до листов и вывести их
значения.
Пример
Промоделируем
два запроса, приведенные в примере. Разобьем отрезки запросов на
фундаментальные:
·
[1; 3] = [1; 3];
·
[2; 4] = [2; 2] + [3; 3] + [4; 4].
Реализация алгоритма
Объявим дерево отрезков
#define MAX 300010
long long
SegTree[4*MAX];
int i, n, m, l, r;
long long
x;
Процедура проталкивания.
void Push(int
Vertex, int LeftPos, int
Middle, int RightPos)
{
if
(SegTree[Vertex])
{
SegTree[2*Vertex] = max(SegTree[2*Vertex],SegTree[Vertex]);
SegTree[2*Vertex+1] =
max(SegTree[2*Vertex+1],SegTree[Vertex] +
Middle - LeftPos + 1);
SegTree[Vertex] = 0;
}
}
Продажа шапок на промежутке [Left;
Right] начиная с цены x.
void Update(int
Vertex, int LeftPos, int
RightPos,
int
Left, int Right, long
long x)
{
if (Left >
Right) return;
if ((LeftPos
== Left) && (RightPos == Right))
SegTree[Vertex] = max(SegTree[Vertex],x);
else
{
int Middle
= (LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
int len =
min(Middle,Right) - Left + 1;
if (len
< 0) len = 0;
Update(2*Vertex, LeftPos, Middle, Left,
min(Middle,Right), x);
Update(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1), Right, x + len);
}
}
Произведем проталкивание до листов и выведем состояние
массива.
void PrintResult(int
Vertex, int LeftPos, int
RightPos)
{
if (LeftPos
== RightPos)
printf("%lld
",SegTree[Vertex]);
else
{
int Middle
= (LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
PrintResult(2*Vertex, LeftPos, Middle);
PrintResult(2*Vertex+1, Middle+1,
RightPos);
}
}
Основная часть программы. Читаем входные данные.
scanf("%d %d", &n, &m);
memset(SegTree,0,sizeof(SegTree));
Обрабатываем m запросов.
for(i = 0; i < m; i++)
{
scanf("%d %d
%lld", &l, &r, &x);
Update(1,1,n,l,r,x);
}
Выводим результат.
PrintResult(1,1,n);
printf("\n");